package com.lxq.LeetCode.findMedianSortedArrays;

public class Solution {
    public static void main(String[] args) {
        int[] nums1 = {2, 2, 2}, nums2 = {2, 2, 2, 2};
        double res = findMedianSortedArrays(nums1, nums2);
        System.out.println(res);
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double res = 0;
        if (nums1.length == 0 && nums2.length != 0) {
            if (nums2.length % 2 == 0) {
                res = (double) (nums2[nums2.length / 2 - 1] + nums2[nums2.length / 2]) / 2D;
            } else {
                res = nums2[nums2.length / 2];
            }

            return res;
        }
        if (nums2.length == 0 && nums1.length != 0) {
            if (nums1.length % 2 == 0) {
                res = (double) (nums1[nums1.length / 2 - 1] + nums1[nums1.length / 2]) / 2D;
            } else {
                res = nums1[nums1.length / 2];
            }
            return res;
        }

        int arrayLength = nums1.length + nums2.length;
        if (arrayLength % 2 == 0) {
            double x1 = 1000001, x2 = 1000001;
            int p1 = arrayLength / 2, p2 = p1 + 1;
            int i = 0, j = 0;
            int num = 0;
            boolean flag1 = true, flag2 = true;
            while (x1 == 1000001 || x2 == 1000001) {
                num++;
                if (flag1 && nums1[i] <= nums2[j]) {
                    if (num == p1) {
                        x1 = nums1[i];
                    }
                    if (num == p2) {
                        x2 = nums1[i];
                    }
                    i++;
                    if (i == nums1.length) {
                        i--;
                        flag1 = false;
                        nums1[i] = 1000001;
                    }

                } else if (flag2 && nums2[j] < nums1[i]) {
                    if (num == p1) {
                        x1 = nums2[j];
                    }
                    if (num == p2) {
                        x2 = nums2[j];
                    }
                    j++;
                    if (j == nums2.length) {
                        j--;
                        flag2 = false;
                        nums2[j] = 1000001;
                    }
                }

            }

            res = (x1 + x2) / 2D;
        } else {
            double x1 = 1000001;
            int p1 = arrayLength / 2 + 1;
            int i = 0, j = 0;
            int num = 0;
            boolean flag1 = true, flag2 = true;
            while (x1 == 1000001) {
                num++;
                if (flag1 && nums1[i] <= nums2[j]) {
                    if (num == p1) {
                        x1 = nums1[i];
                    }
                    i++;
                    if (i== nums1.length){
                        i--;
                        flag1 = false;
                        nums1[i] = 1000001;
                    }
                } else if(flag2 && nums2[j] < nums1[i]) {
                    if (num == p1) {
                        x1 = nums2[j];
                    }
                    j++;
                    if (j== nums2.length){
                        j--;
                        flag2 = false;
                        nums2[j] = 1000001;
                    }
                }
            }


            res = x1;
        }

        return res;
    }
}
